/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  //  vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
//
    //}
    string DFSFindSeq(TreeNode* root, vector<TreeNode*>& res, unordered_map<string, int>& map)
	{
	
			//这个函数要做的事情就是，每一个访问的记录都存起来，放到map中并和map原来的作比较，若有则记录到结果中
		if (root == nullptr)
		{
			return "";
		}

		string str_tmp = to_string(root->val) + "," + DFSFindSeq(root->left,res,map) + "," + DFSFindSeq(root->right, res, map);
		if (map[str_tmp] == 1)
		{
			res.push_back(root);
		}
		map[str_tmp]++;
		return str_tmp;
	}
	
	vector<TreeNode*> findDuplicateSubtrees(TreeNode* root)
	{
		//主入口
		vector<TreeNode*> res; //会存放重复的
		unordered_map<string, int> map;
		DFSFindSeq(root,res,map);
		return res;

	}
};